//和为k的子数组
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) 
    {
        //暴力遍历时间复杂度高 因为求每个子数组的和的时间都是 O(n)
        //使用一个数组 sum 计算出 nums 的前 i 个元素的和（即前缀和），
        //即 sum[i] 代表 sum 的前 i 个元素的和，
        //那么对于任意子数组的和 SUM(nums(j : i)) = sum[i] - sum[j - 1]，
        //可以把求每个子数组的和的时间降为 O(1)。

        //这样写好之后 依然需要O(N^2)的时间复杂度寻找每一个sum[i]
        //寻找让其成立的sum[j]
        //这样的时间复杂度可以通过哈希表解决 
        if(nums.empty()) return 0;
        int n=nums.size();
        //vector<int>preSum(n+1,0);
        map<int,int>preSum;
        preSum[0]=1;
        int res=0;
        int sum=0;
        for(int i=0;i<n;i++)
        {
            //preSum[i+1]=preSum[i]+nums[i];
            sum+=nums[i];
            res+=preSum[sum-k];
            preSum[sum]++;
           
        }
        return res;
    }
};
